#include "main.h"
#include "timeout.h"

#define TVN_BITS (4)
#define TVN_SIZE (1 << TVN_BITS)
#define TVN_MASK (TVN_SIZE - 1)

#define RANGE(x) (1 << ((x) * TVN_BITS))
#define INDEX(x, y) (((x) >> ((y) * TVN_BITS)) & TVN_MASK)

#define MAXIMUM_TIMEOUT (0xffff)

LIST_HEAD(tvec_head, timeout_s);

struct tvec_base_s {
	struct tvec_head tv1[TVN_SIZE];
	struct tvec_head tv2[TVN_SIZE];
	struct tvec_head tv3[TVN_SIZE];
	struct tvec_head tv4[TVN_SIZE];
};

static struct tvec_base_s base;

void add_timeout(timeout_t* timeout)
{
	time_t expires = timeout->expires;
	time_t idx = expires - current_time;
	struct tvec_head *head;

	if (expires < current_time) {
		/*
		 * Can happen if you add a timeout with expires == current_time,
		 * or you set a timeout to go off in the past
		 */
		head = base.tv1 + INDEX(current_time, 0);
	} else if (idx < RANGE(1)) {
		head = base.tv1 + INDEX(expires, 0);
	} else if (idx < RANGE(2)) {
		head = base.tv2 + INDEX(expires, 1);
	} else if (idx < RANGE(3)) {
		head = base.tv3 + INDEX(expires, 2);
	} else {
		/* If the timeout is larger than MAXIMUM_TIMEOUT
		 * then we use the MAXIMUM_TIMEOUT
		 */
		if (idx > MAXIMUM_TIMEOUT) {
			expires = MAXIMUM_TIMEOUT + current_time;
		}
		head = base.tv4 + INDEX(expires, 3);
	}
	/* FIFO */
	LIST_INSERT_HEAD(head, timeout, entry);

	debug_message("insert timeout at %d, expire at %d\n", current_time, expires);
}

static int cascade(struct tvec_head *head, int index)
{
	timeout_t *timeout, *tmp;

	/* Cascade all the timeouts from tv up one level */
	LIST_FOREACH_SAFE(timeout, head + index, entry, tmp) {
		LIST_REMOVE(timeout, entry);
		add_timeout(timeout);
	}

	return index;
}

void run_timeout()
{
	struct tvec_head *head;
	timeout_t *timeout;

	time_t real_time = get_current_time();
	while(current_time <= real_time) {
		int index = current_time & TVN_MASK;

		/* Cascade timeouts */
		if (!index && (!cascade(base.tv2, INDEX(current_time, 1)))
				&& (!cascade(base.tv3, INDEX(current_time, 2)))) {
			cascade(base.tv4, INDEX(current_time, 3));
		}

		head = base.tv1 + index;
		while(!LIST_EMPTY(head)) {
			timeout = LIST_FIRST(head);
			LIST_REMOVE(timeout, entry);

			(*timeout->func)(timeout->arg);
		}

		current_time++;
	}
}

void del_timeout(timeout_t *timeout)
{
	LIST_REMOVE(timeout, entry);
}
